//给你一个 n x n 矩阵 matrix ，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。 
//请注意，它是 排序后 的第 k 小元素，而不是第 k 个 不同 的元素。 
//
// 
//
// 示例 1： 
//
// 
//输入：matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8
//输出：13
//解释：矩阵中的元素为 [1,5,9,10,11,12,13,13,15]，第 8 小元素是 13
// 
//
// 示例 2： 
//
// 
//输入：matrix = [[-5]], k = 1
//输出：-5
// 
//
// 
//
// 提示： 
//
// 
// n == matrix.length 
// n == matrix[i].length 
// 1 <= n <= 300 
// -109 <= matrix[i][j] <= 109 
// 题目数据 保证 matrix 中的所有行和列都按 非递减顺序 排列 
// 1 <= k <= n2 
// 
// Related Topics 数组 二分查找 矩阵 排序 堆（优先队列） 
// 👍 690 👎 0

package com.cute.leetcode.editor.cn;
public class KthSmallestElementInASortedMatrix {
    public static void main(String[] args) {
        Solution solution = new KthSmallestElementInASortedMatrix().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 题解中并不是要对数组进行遍历，而是使用二分法进行统计元素个数
         * left初始值取矩阵最小的那一个，right取最大的那一个，目标元素肯定在left和right之间
         * 取left和right的中间值为mid
         * 统计数组中<=mid的元素个数为n
         *  如果n<k：则说明目标元素肯定要比mid大，所以left直接设置为mid+1 right不变继续统计
         *  不然就将right赋值为mid
         *  直到left == right的时候就找到了目标值，返回right就可以了
         */
        public int kthSmallest(int[][] matrix, int k) {
            int row = matrix.length;
            int col = matrix[0].length;
            int left = matrix[0][0];
            int right = matrix[row-1][col-1];
            while (left < right){
                //TODO 这里要写成以下这种形式，两个int直接相加可能发生越界，本案例还真不会通过
                int mid = left + (right - left) / 2;
                int count = countNum(matrix,mid,row,col);
                if (count<k){
                    left = mid+1;
                }else right = mid;
            }
            return right;
        }

        /**
         * 统计当前矩阵中<=mid元素的个数，从左下角的元素作为起始元素
         * 如果val<=mid，则说明当前列都<=mid，结果加上 row +1 且col++ 到下一列去进行比较
         * 否则row--去上一行进行比较
         * 因为矩阵中<=mid的元素必然在左上部分，可以被一条路径分割出来，可以参照官方的题解看一下
         */
        private int countNum(int[][] matrix,int mid, int row, int col) {
            int res = 0;
            int r = row-1;
            int c = 0;
            while ( r>=0 && c<col){
                if (matrix[r][c]<=mid){
                    res += r+1;
                    c++;
                }else r--;
            }
            return res;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}